#include <iostream>
#include <queue>
#include <vector>

/**
 * PAT A 1018 Public Bike Management
 */

struct Edge {
    int to;
    int len;

    Edge(int to, int len) : to(to), len(len) {}
};

struct Vertex {
    int index;
    std::vector<Edge> edges;
    int nBikes;

    int dist;
    std::vector<int> prev;

    Vertex(int index, int num) : index(index), nBikes(num), dist(INT32_MAX) {}
};

struct VertexCmp {
    bool operator()(const Vertex *u, const Vertex *v) const {
        return u->dist > v->dist;
    }
};

int maxCap;
std::vector<Vertex> vertices;

void shortestPath(int from, int to) {
    // Initialization
    std::priority_queue<Vertex *, std::deque<Vertex *>, VertexCmp> heap;
    Vertex *fromVert = &vertices[from];
    fromVert->dist = 0;
    heap.push(fromVert);

    // Run Dijkstra algorithm
    while (!heap.empty()) {
        // Pop one vertex
        Vertex *u = heap.top();
        heap.pop();

        // Add neighbors to heap
        for (int i = 0; i < u->edges.size(); i++) {
            Edge *edge = &u->edges[i];
            int to = edge->to;
            Vertex *v = &vertices[to];
            int newDist = u->dist + edge->len;
            if (newDist <= v->dist) {
                if (newDist != v->dist) {
                    v->dist = newDist;
                    v->prev.clear();
                }
                int found = false;
                for (auto x : v->prev)
                    if (x == u->index) {
                        found = true;
                        break;
                    }
                if (found) continue;
                v->prev.push_back(u->index);
                heap.push(v);
            }
        }
    }
}

int minNeed = INT32_MAX, minRemain = INT32_MAX;

std::vector<int> path, optPath;

void search(int idx, int depth) {
    // Reaching PBMC, check number of needed and remaining bikes
    if (idx == 0) {
        int need = 0, remain = 0;
        for (int i = depth - 1; i >= 0; i--) {
            Vertex &v = vertices[path[i]];
            int diff = v.nBikes - maxCap / 2 + remain;
            if (diff < 0) {  // should take more bikes from PBMC
                need -= diff;
                remain = 0;
            } else if (diff > 0)  // current bikes can satisfy
                remain = diff;
        }
        if (need < minNeed || (need == minNeed && remain < minRemain)) {
            minNeed = need;
            minRemain = remain;
            optPath = std::vector<int>(path.begin(), path.begin() + depth);
        }
    }

    // Search previous node in shortest paths
    path[depth] = idx;
    Vertex &v = vertices[idx];
    for (int i = 0; i < v.prev.size(); i++) search(v.prev[i], depth + 1);
}

int main() {
    // Read graph
    int nStat, problem, nEdges;
    scanf("%d %d %d %d", &maxCap, &nStat, &problem, &nEdges);
    vertices.push_back(Vertex(0, 0));
    for (int i = 1; i <= nStat; i++) {
        int num;
        scanf("%d", &num);
        vertices.push_back(Vertex(i, num));
    }
    for (int i = 0; i < nEdges; i++) {
        int from, to, len;
        scanf("%d %d %d", &from, &to, &len);
        vertices[from].edges.push_back(Edge(to, len));
        vertices[to].edges.push_back(Edge(from, len));
    }

    // Find shortest path
    shortestPath(0, problem);

    // DFS the shortest paths to find optimal solution
    path = std::vector<int>(vertices.size());
    search(problem, 0);
    printf("%d 0", minNeed);
    for (int i = optPath.size() - 1; i >= 0; i--) printf("->%d", optPath[i]);
    printf(" %d\n", minRemain);

    return 0;
}
